﻿/*
题目: 最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

https://leetcode.cn/problems/making-a-large-island/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
#define MIN_ISLAND_ID 2

public:
    int dirs[5] = { 0, -1, 0, 1, 0 };
    int n, m;

    int largestIsland(vector<vector<int>>& grid) {
        int res = 0;
        n = grid.size(), m = grid[0].size();

        int id = 2;                             // 为每个岛进行编号，从 2 号开始
        unordered_map<int, int> island_area;    // 每个岛屿的面积
        vector<pair<int, int>> spaces;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0)    spaces.emplace_back(i, j);
                else if (grid[i][j] == 1) {
                    int cur = area(grid, i, j, id);
                    island_area.emplace(id, cur);

                    res = max(res, cur);
                    id++;
                }
            }
        }

        for (auto& [x, y] : spaces) {
            int sum = 1;
            unordered_set<int> arround;
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i];
                int ny = y + dirs[i + 1];
                if (ok(nx, ny) && grid[nx][ny] >= MIN_ISLAND_ID && arround.count(grid[nx][ny]) == false) {
                    arround.insert(grid[nx][ny]);
                    sum += island_area[grid[nx][ny]];
                }
            }

            res = max(res, sum);
        }

        return res;
    }

    int area(vector<vector<int>>& grid, int x, int y, const int id) {
        grid[x][y] = id;

        int sum = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i];
            int ny = y + dirs[i + 1];

            if (ok(nx, ny) && grid[nx][ny] != id && grid[nx][ny] > 0) {
                sum += area(grid, nx, ny, id);
            }
        }

        return sum;
    }

    bool ok(int x, int y) {
        return x >= 0 && x < n&& y >= 0 && y < m;
    }
};
